
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (NULL == head) return NULL;
        Node* node = head;
        while (node)
        {
            Node* newNode = new Node(node->val);
            newNode->next = node->next;
            node->next = newNode;
            node = node->next->next;
        }
        Node* front = head;
        while (front)
        {
            Node* newNode = front->next;
            newNode->random = (front->random != NULL) ? front->random->next : NULL;
            front = front->next->next;
        }
        Node* New = head->next;
        Node* cur = head;
        while (cur)
        {
            Node* newNode = cur->next;
            cur->next = cur->next->next;
            newNode->next = (newNode->next != NULL) ? newNode->next->next : NULL;
            cur = cur->next;
        }
        return New;
    }
};